1. Field of the Invention
The present invention relates to a system and method for enabling wired access points on a core network of an ad-hoc communications network to identify the locations of wireless nodes in the network. More particularly, the present invention relates to a system and method for providing route tracing between a wireless node and an access point such that route tracing information can be included with data packets communicated between the node and access point for allowing the access point to identify approximately where to locate a particular node that has changed its position.
2. Description of the Related Art
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed for use by the military. In this type of network, each user terminal (hereinafter “mobile node”) is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Accordingly, data packets being sent from a source mobile node to a destination mobile node are typically routed through a number of intermediate mobile nodes before reaching the destination mobile node. Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other types of user terminals, such as those on the public switched telephone network (PSTN) and on other networks such as the Internet. Details of these types of ad-hoc networks are described in U.S. Pat. No. 7,072,650 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, issued on Jul. 4, 2006, in U.S. Pat. No. 6,807,165 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, issued on Oct. 19, 2004, and in U.S. Pat. No. 6,873,839 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, issued on Mar. 29, 2005, the entire content of each of said patent applications being incorporated herein by reference.
As can be appreciated by one skilled in the art, a wireless ad-hoc network has mobile nodes, some of which are in constant or relatively constant motion. Hence, the location of any given mobile node in the network may be changing continuously at a variable rate, up to a maximum rate of change. The maximum rate of change can be, for example, the speed of vehicles in which the mobile nodes are employed. Due to this constant motion, the ability for any node in the network, or entities outside the network, to find nodes and determine how to route packets to a destination node can be difficult.
For instance, if each node in the network was always aware of the location of all other nodes, it would be a simple matter for a node to find a particular node and route data packets to that node. However, when nodes are mobile, every time a node moves, the other nodes have to be informed of the move, and update their information pertaining to the moving node so as to keep track of the moving node. These update can consume a large amount of the available bandwidth of the network, leaving less bandwidth available to transmit data.
To overcome this problem due to the limited amount of system resources available for updates, the knowledge that each node can possess with regard to its neighbors can be limited to a small subset of nodes. For example, each node can have knowledge of its immediate neighbors within its transmission range, and each of its neighbors' neighbors. In other words, each node could have knowledge of nodes a certain number of hops away, such as two hops away or less. Naturally, each node can have knowledge of other nodes that are a larger number of hops away, but the overhead necessary to keep track of the network grows exponentially as the number of hops is increased.
If the knowledge that a node possesses with regard to other nodes is limited to nodes a certain number of hops away (e.g., two-hops away), an additional mechanism is therefore needed to enable a node to locate nodes outside of this range. Specifically, an access point performs a broadcast flood to query each node within its broadcast range to determine whether any of those nodes have knowledge about another node of interest. That is, the access point sends a message that is received by each of its neighbors within it broadcast range. The nodes in turn send a similar message to the nodes in each of their broadcast ranges. This process continues out to the finite number of hops defined to be the access point's maximum coverage area. Accordingly, all nodes served by an access point are contacted, even those having no knowledge of the node of interest. The broadcast flood mechanism therefore places a huge burden on the network due to the overwhelming number of broadcasts required, and thus significantly wastes network bandwidth resources.
Accordingly, a need exists for a system and method capable of effectively and efficiently monitoring the approximate locations mobile nodes while using only minimal network bandwidth resources.